package com.zhugang.week07;

/**
 * @program algorithms
 * @description: LowestCommonAncestorBySearchTree
 * @author: chanzhugang
 * @create: 2022/07/27 13:05
 */
public class LowestCommonAncestorBySearchTree2 {

    /**
     * 剑指offer 68-I 二叉搜索树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归解法
        if (p == root || q == root || (p.val < root.val && root.val < q.val) || (q.val < root.val && root.val < p.val)) {
            return root;
        }
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}